A merge operation is a common editing operation for combining two or more textual documents or other types of sequences together. The documents to be merged may be, for example, different versions of software source code with modifications by different software developers, or different versions of a word-processing document edited on different machines. The documents to be merged typically contain some common parts and some parts that are different, and overlapping differences are viewed as conflicts that may require the input of a user to resolve the conflicts, i.e., picking the parts from the right version to be included in the final merged document. For instance, if the documents are source code files containing conflicting changes, the user would have to decide which changes are the correct ones that should be kept. To assist the user in resolving the conflicts, the editing application performing the merge has to be able to provide a representation of the differences and common parts of the documents being merged in a clear manner.
A three-way merge operation, as indicated by its name, has three sequences of elements as its inputs. Typically, the three sequences include one sequence designated as an original version (“the Original”) and two versions, Version1 and Version2, that in many cases are derived from the original. For example, the three sequences may correspond to an original source code file, a first modified version of the source code with changes made by one developer, and a second modified version of the source code containing changes made by another developer. Conventionally, the representation of a conflict in a three-way merge operation of three textual documents involves an “original chunk” of text found in the original but not in its entirety in both Version1 and Version2, a “difference chunk” of text that is found in Version1 but not in the original, and a second difference chunk of text found in Version2 but not in the original. The user can then select, based on the conflict representation, the original chunk or either the difference chunk of Version1 or the difference chunk of Version2.
One problem with this conventional approach of representing conflicts in a three-way merge is that it does not provide sufficiently fine granularity in the comparison. For instance, it is common for the original chunk to share a substantial portion of text with either or both of the difference chunks of Version1 and Version2. The different chunks of Version1 and Version2 may also share some common parts. The real differences between any two of the three versions may be embedded in the conflicting chunks and require the user to closely examine the chunks to identify them. As a result, the conventional representation of conflicts in a 3-way merge can be confusing to the user and does not fully assist the user in identifying the real differences between the different versions in order to resolve the conflicts.